package divide.easy;

/**
 * 1. 问题描述
 *      输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 *
 * 2. 算法分析
 *      主要分析分治的思路：
 *          此题是一道非常经典的题，也是需要教课书中的一道问题，可以采用暴力的方式实现起来非常简单
 *          一般对于链表的题目而言，大多都可以采用递归的方式来实现，，下面给出分治的思路(本质也是使用递归实现的)
 *          假设当前有两个有序链表l1,l2，分下下面的两种状态：
 *              1. l1当前的头节点的val < l2当前头节点的val
 *                 此时我们需要以l1的头节点为起始，然后将l1.next与l2继续合并
 *              2. l1.val > l2.val
 *                 此时需要以l2的头节点为起始，然后l2.next与l1继续合并
 *          显然上述是一个递归的过程
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q002_合并两个排序的链表 {

    public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}
